#include <iostream>
using namespace std;

typedef int QElemType;

typedef struct Qnode {
    QElemType data;	// 数据域
    Qnode * next;	// 指针域
}Qnode, *QueuePtr;

typedef struct {
    QueuePtr front;   // 头指针
    QueuePtr rear;    // 尾指针
}LinkQueue;

bool InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (QueuePtr) malloc(sizeof(Qnode)); // 生成头结点，并让front和rear指向它
    if (!Q.front)
        return false;
    Q.front->next = NULL;  // 头结点的指针域置空
    return true;
}

// 入队
bool EnQueue(LinkQueue &Q, QElemType e)
{
    QueuePtr p = (QueuePtr) malloc(sizeof(Qnode));
    if (!p)
        return false;
    p->data = e;        // 将新结点数据域置为e
    p->next = NULL; Q.rear->next = p;  // 将新结点插入到队尾
    Q.rear = p;         // 修改队尾指针
    return true;
}

// 出队
bool DeQueue(LinkQueue &Q, QElemType &e)
{
    if (Q.front == Q.rear)
        return false;
    QueuePtr p = Q.front->next;     // p 指向队头元素
    e = p->data;
    Q.front->next = p->next;    // 修改头指针
    if (Q.rear == p)    // 最后一个元素被删，队尾指针指向头结点
        Q.rear = Q.front;
    free(p);
    return true;
}

// 销毁链队列
bool DestoryQueue(LinkQueue &Q)
{
    QueuePtr p;
    while (Q.front)
    {
        p = Q.front->next;
        free(Q.front);
        Q.front = p;
    }
    return true;
}

// 取队头
bool GetHead(LinkQueue Q, QElemType &e)
{
    if (Q.front != Q.rear)  // 队列非空
        e = Q.front->next->data;
    return true;
}